/**
 * //你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上
 * //被小偷闯入，系统会自动报警。
 * //
 * // 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：[1,2,3,1]
 * //输出：4
 * //解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * //     偷窃到的最高金额 = 1 + 3 = 4 。
 * //
 * // 示例 2：
 * //
 * //
 * //输入：[2,7,9,3,1]
 * //输出：12
 * //解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 * //     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 100
 * // 0 <= nums[i] <= 400
 * //
 * //
 * // Related Topics 数组 动态规划 👍 2256 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00198HouseRobber {
    public static void main(String[] args) {
        Solution solution = new ID00198HouseRobber().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int rob(int[] nums) {


            int n = nums.length;

            //一个状态记录所有的格子从左开始往右偷，能达到的最大值，最大值就出现在倒数第一个格子的两种状态里
            //所有格子都是 偷 和 不偷 两种个状态
            int[][] sums = new int[n][2];


            //初始化第一个格子，无法从左边推导出来。
            sums[0][1] = nums[0]; //只用初始化偷的状态

            //动态规划
            //从1开始，每个格子有两种状态，
            for (int i = 1; i < n; i++) {
                // 如果当前格子 不偷，需要从上个格子的偷和不偷两个状态对比得来
                sums[i][0] = Math.max(sums[i - 1][0], sums[i - 1][1]);

                // 如果当前格子 偷，只能从上个格子的不偷状态推导过来
                sums[i][1] = sums[i - 1][0] + nums[i];
            }


            return Math.max(sums[n - 1][0], sums[n - 1][1]);


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}